package cn.ldw.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class CombinationSum {
    public static void main(String[] args) {
        int[] candidates = {10,1,2,7,6,1,5};
        List<List<Integer>> lists = combinationSum2(candidates, 8);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
        Stack s = new Stack();
    }
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        for(int i = 0; i < candidates.length; i++) {
            if(candidates[i] > target) {
                return ans;
            }
            if(i > 0 && candidates[i-1] == candidates[i]) {
                continue;
            }
            int left = i + 1;
            int right = candidates.length-1;
            while(left < right) {
                int sum = candidates[i] + candidates[left] + candidates[right];
                if(sum == target) {
                    List<Integer> t = new ArrayList<>();
                    t.add(candidates[i]);
                    t.add(candidates[left]);
                    t.add(candidates[right]);
                    ans.add(t);
                    while(left < right && candidates[left] == candidates[left + 1]) {
                        left++;
                    }
                    while(left < right && candidates[right] == candidates[right-1]) {
                        right--;
                    }
                    left++;
                    right--;
                }
                else if(sum < target) {
                    left++;
                }
                else {
                    right--;
                }
            }
        }
        return ans;
    }
}
